INF = 1000000001  # 设置无穷大，用来表示无法到达
N = 510  # 最大节点数
dp = [[INF] * N for _ in range(N)]  # 创建二维数组 dp，用来存储最短路径
n, m = 0, 0  # n是节点数，m是边数

def floyd():
    # Floyd-Warshall 算法的三重循环
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

# 输入节点数和边数
n, m = map(int, input().split())

# 初始化dp数组，dp[i][j]表示从i到j的最短路径
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            dp[i][j] = 0  # 自己到自己距离为0
        else:
            dp[i][j] = INF  # 初始设置为无穷大

# 输入图的边
for _ in range(m):
    u, v, w = map(int, input().split())
    dp[u][v] = min(dp[u][v], w)  # 只保留最短的边

# 执行Floyd-Warshall算法
floyd()

# 输出从节点1到节点n的最短路径
if dp[1][n] == INF:
    print(-1)  # 如果不可达，输出 -1
else:
    print(dp[1][n])  # 输出最短路径